package com.le.enhance.class5;

import org.junit.Test;

/**
 * 二叉树中，一个节点可以往上走和往下走，那么从节点A总能走到节点 B。
 * 节点A走到节点B的距离为：A走到B最短路径上的节点个数。
 * 求一棵二叉树上的最远距离
 */
public class Code_03_MaxDistanceInTree {

    public static class Node {
        public int value;
        Node left;
        Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class ReturnType {
        public int maxDistance;
        public int height;

        public ReturnType(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }

    public static int getMaxDistance(Node head){
        return process(head).maxDistance;
    }

    public static ReturnType process(Node head) {
        if (head == null) {
            return new ReturnType(0, 0);
        }
        ReturnType leftInfo = process(head.left);
        ReturnType rightInfo = process(head.right);

        return new ReturnType(
                Math.max(Math.max(leftInfo.maxDistance, rightInfo.maxDistance), leftInfo.height + rightInfo.height + 1),
                Math.max(leftInfo.height, rightInfo.height) + 1
        );
    }

    @Test
    public void test1(){
        Node head1 = new Node(1);
        head1.left = new Node(2);
        head1.right = new Node(3);
        head1.left.left = new Node(4);
        head1.left.right = new Node(5);
        head1.right.left = new Node(6);
        head1.right.right = new Node(7);
        head1.left.left.left = new Node(8);
        head1.right.left.right = new Node(9);
        System.out.println(getMaxDistance(head1));
    }

    @Test
    public void test2(){
        Node head2 = new Node(1);
        head2.left = new Node(2);
        head2.right = new Node(3);
        head2.right.left = new Node(4);
        head2.right.right = new Node(5);
        head2.right.left.left = new Node(6);
        head2.right.right.right = new Node(7);
        head2.right.left.left.left = new Node(8);
        head2.right.right.right.right = new Node(9);
        System.out.println(getMaxDistance(head2));
    }
}
